package com.cat.dynamicPlanning02;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/maximum-number-of-points-with-cost/description/
 * @create 2025/9/11 20:47
 * @since JDK17
 */

public class Solution01 {
    public long maxPoints(int[][] points) {
        int n = points.length, m = points[0].length;
        long[][] dp = new long[n][m];
        for (int i = 0; i < m; i++) {
            dp[0][i] = points[0][i];
        }
        for (int i = 1; i < n; i++) {
            long l = Long.MIN_VALUE;
            for (int j = 0; j < m; j++) {
                l = Math.max(l, dp[i - 1][j] + j);
                dp[i][j] = Math.max(dp[i][j], l + points[i][j] - j);
            }
            long r = Long.MIN_VALUE;
            for (int j = m - 1; j >= 0; j--) {
                r = Math.max(r, dp[i - 1][j] - j);
                dp[i][j] = Math.max(dp[i][j], r + points[i - 1][j] + j);
            }
        }

        return Arrays.stream(dp[n - 1]).max().getAsLong();
    }
}
